package com.coinland.study;

import java.util.Queue;
import java.util.Stack;

/**
 * 类描述:
 * 创建人:  shenZ
 * 创建时间: 2019/9/11
 * 联系方式: 252079249@qq.com
 * 修改时间: 2019/9/11
 */
public class Test {


//~~~~~~~~~~~~~~~~~~~~~~~~~~ 栈  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /**
     * 栈-- 先进后出
     * 进栈测试
     */
    public void stackPush(){
        Stack objStackPush = new Stack();
        objStackPush.push("shenZ");
        objStackPush.push("baba");
        objStackPush.push("mama");
        objStackPush.push("yudujuan");
        objStackPush.push("shenhui");

        Object[] arrays = objStackPush.toArray();
        for (Object o: arrays
             ) {
            System.out.println(o.toString());
        }

    }

    /**
     * 栈-- 先进后出
     * 出栈测试
     */
    public void stackPop(){
        Stack objStackPush = new Stack();
        objStackPush.push("yuefu");
        objStackPush.push("yuemu");


        Object[] arrays = objStackPush.toArray();
        for (Object o: arrays
                ) {
            System.out.println(o.toString());
        }
        System.out.println();
        System.out.println(objStackPush.pop());
        System.out.println(objStackPush.pop());
    }

    // https://www.jianshu.com/p/04efb56e7018
    //~~~~~~~~~~~~~~~~~~~~~~~~~~ 冒泡排序  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    public void bubbleSort(int[] source){
        int length = source.length;
        int temp = 0;
        for (int i=0;i<length-1;i++){
            for(int j=0;j<length-i-1;j++){
                if(source[j]>source[j+1]){
                    temp = source[j];
                    source[j] = source[j+1];
                    source[j+1] = temp;
                }
            }
        }
    }

    //~~~~~~~~~~~~~~~~~~~~~~~~~~ 快速排序  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    /**
     * 快速排序
     * @param arr   数据源
     * @param left  起始数据的位置
     * @param right   结束数据的位置
     */
    public static void quickSort(int[] arr, int left, int right){
        if(right > left) {
            int midst = findMidst(arr, left, right); //找到基准点
            quickSort(arr, left, midst); //对左侧排序
            quickSort(arr, midst + 1, right); //对右侧排序
        }
    }

    public static int findMidst(int[] arr, int left, int right) {
        int midst = arr[left];
        while(right > left) {
            //从右向左循环，找到比基准数小的
            while(right>left&&arr[right] >= midst) {
                right--;
            }
            arr[left] = arr[right];
            //从左向右循环，找到比基准数大的
            while(right>left&&arr[left] <= midst) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = midst;
        return left;
    }

    //~~~~~~~~~~~~~~~~~~~~~~~~~~ 插入排序  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    public void insertSort(int[] source) {
        if (source != null && source.length > 1) {
            for (int i = 1; i < source.length; i++) {
                int temp = source[i]; //要插入的数据
                int j;
                for (j = i - 1; j >= 0; j--) {
                    if (source[j] > temp) {
                        source[j + 1] = source[j];
                    } else {
                        break;
                    }
                }
                //此处注意 j会先-1，在判断j是否符合条件，故需要+1
                source[j + 1] = temp;
            }
        }
    }


    //~~~~~~~~~~~~~~~~~~~~~~~~~~ 选择排序法  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


    public void selectSort(int[] source) {
        int pos;
        int temp;
        for (int i = 0; i < source.length; i++) {
            pos = i;
            for (int j = i + 1; j < source.length; j++) {
                if (source[j] < source[pos]) {
                    pos = j;
                }
            }
            if (pos != i) {
                temp = source[pos];
                source[pos] = source[i];
                source[i] = temp;
            }
        }
    }


    //~~~~~~~~~~~~~~~~~~~~~~~~~~ 希尔排序法  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    public void shellSort(int[] arr){
        if (arr != null && arr.length > 2) {
            int index = arr.length / 2;
            while (true) {
                for (int i = 0; i < index; i++) {
                    for (int j = i; j + index < arr.length; j += index) {
                        if(arr[j] > arr[j+index]) {
                            int temp = arr[j];
                            arr[j] = arr[j + index];
                            arr[j+ index] = temp;
                        }
                    }
                }
                if(index == 1) {
                    break;
                }
                index--;
            }
        }
    }

    //~~~~~~~~~~~~~~~~~~~~~~~~~~ 二分查找法  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    /**
     * 递归实现
     * @param arr
     * @param start
     * @param end
     * @param target
     * @return
     */
    public  int binarySort(int[] arr, int start, int end, int target) {
        int middle = (start + end) / 2;
        if(arr[end] < target || arr[start] > target || start > end) {
            return -1;
        }

        if (arr[middle] == target) {
            return middle;
        } else if (arr[middle] > target) {
            return binarySort(arr, middle + 1, end, target);
        } else{
            return binarySort(arr, 0, middle - 1, target);
        }

    }

    /**
     * 循环实现
     * @param arr
     * @param target
     * @return
     */
    public int binarySort(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;
        while(start <= end) {
            int middle = (start + end) / 2;
            if(arr[middle] == target) {
                return middle;
            }else if(arr[middle] > target) {
                start = middle +1;
            }else {
                end = middle - 1;
            }
        }

        return -1;
    }


}
